#include <stdbool.h>

typedef int (*cmp_func)(void *p1, void *p2);
typedef bool (*equal_func)(void *p1, void *p2);

/**
 * used for search_max_subarray
 */
typedef struct
{
    long left, right;
    long value;
} Sub_Array;

/**
 * insert sort
 * array: array address
 * size: element size
 * num: element number
 * cmp_func: compare function
 */
void insert_sort(void *array, int size, int num, cmp_func cmp);

/**
 * merge sort
 * array: array address
 * size: element size
 * p: start suffix
 * r: end suffix (include)
 * cmp_func: compare function
 */
void merge_sort(void *array, int size, long p, long r, cmp_func cmp);

/**
 * search max subarray
 * array: array address
 * low: start suffix(include)
 * high: end suffix(include)
 */
Sub_Array search_max_subarray(long *array, long low, long high);

/**
 * from raw array to build a heap
 * array: array address
 * size: element size
 * num: element number
 * cmp: compare function
 */
void build_heap(void *array, int size, long num, cmp_func cmp);

/**
 * use heap to sort a array
 * array: array address
 * size: element size
 * num: element number
 * cmp: compare function
 */
void heap_sort(void *array, int size, long num, cmp_func cmp);

/**
 * heap_extract_max: extract the max element, make the rest a heap
 * heap: heap address
 * size: element size
 * len: input and output, length of the heap
 */
void *heap_extract_max(void *heap, int size, long *len, cmp_func cmp);

/**
 * heap_change_key: change heap[index] to key if cmp(key, heap[index])<0
 * heap: heap address
 * size: element size
 * index: index of the element to change to key
 * key: new key value
 * cmp: compare function
 */
void heap_change_key(void *heap, int size, long index, void *key, cmp_func cmp);

/**
 * heap_insert: insert key into heap
 * heap: heap address
 * size: element size
 * num: heap elements number before insert
 * key: new key value
 * cmp: compare function
 */
void heap_insert(void *heap, int size, long num, void *key, cmp_func cmp);

/**
 * array: array address
 * size: element size
 * p: start suffix in array
 * r: end suffix in array
 * cmp: compare function
 */
void quick_sort(void *array, int size, long p, long r, cmp_func cmp);

/**
 * return the ith element 
 * array: array address
 * size: element size
 * p: start suffix in array
 * r: end suffix in array
 * i: the ith element to be found
 * cmp: compare function
 */
void *select_Ith(void *array, int size, long p, long r, long i, cmp_func cmp);

/**
 * binary tree
 */

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({			\
	const typeof(((type *)0)->member) *__mptr = (ptr);	\
	(type *)((char *)__mptr - offsetof(type, member));	\
})

#define key_of(ptr, type, node, key) ({			\
	const typeof(((type *)0)->node) *__mptr = (ptr);	\
	(void *)((char *)__mptr - offsetof(type, node) + offset(type, key));	\
})

struct binary_tree_node
{
    struct binary_tree_node *parent;
    struct binary_tree_node *left, *right;
};

typedef int (*key_cmp_func)(struct binary_tree_node *node, void *key);
typedef int (*node_cmp_func)(struct binary_tree_node *n1, struct binary_tree_node *n2);

#define init_binary_tree_node(node) { memset(node, 0,  sizeof(*node));}

/**
 * function: search a key in the tree
 * root: root of the tree
 * key: ptr of key value
 * cmp: compare the key included in a node and a bare key
 * return: node of the same key if found, else NULL
 */
struct binary_tree_node *iterative_tree_search(struct binary_tree_node *root, void *key, key_cmp_func cmp);

/**
 * function: search the node of the minimum key
 */
struct binary_tree_node *tree_minimum(struct binary_tree_node *root);

/**
 * function: search the node of the maximum key
 */
struct binary_tree_node *tree_maximum(struct binary_tree_node *root);

/**
 * function: search the successor of the node
 */
struct binary_tree_node *tree_successor(struct binary_tree_node *node);

/**
 * function: search the predecessor of the node
 */
struct binary_tree_node *tree_predecessor(struct binary_tree_node *node);

/**
 * function: insert a node into the tree
 * root: I/O, ptr of root of the tree
 * node: new node to insert
 * cmp: compare function
 */
void tree_insert(struct binary_tree_node **root,
                 struct binary_tree_node *node,
                 node_cmp_func cmp);

/**
 * function: replace u with v, u is picked off the tree
 * root: I/O, ptr of root the tree
 * u: the node to be replaced
 * v: the node to replace u
 */
void transplant(struct binary_tree_node **root, 
                struct binary_tree_node *u,
                struct binary_tree_node *v);

/**
 * function: delete z from tree
 * root: I/O, ptr of root the tree
 * z: the node to be deleted
 */
void tree_delete(struct binary_tree_node **root, struct binary_tree_node *z);


/**
 * red-black tree
 */

#define RB_BLACK    1
#define RB_RED      0

struct rb_tree_node
{
    int color;
    struct rb_tree_node *parent;
    struct rb_tree_node *left, *right;
};

typedef int (*rb_cmp_func)(struct rb_tree_node *n1, struct rb_tree_node *n2);

#define init_rb_tree_node(node) { memset(node, 0,  sizeof(*node));} // init to RB_READ

/**
 * function: search the node of the minimum key
 */
struct rb_tree_node *rb_tree_minimum(struct rb_tree_node *root);

/**
 * function: search the node of the maximum key
 */
struct rb_tree_node *rb_tree_maximum(struct rb_tree_node *root);

/**
 * function: search the successor of the node
 */
struct rb_tree_node *rb_tree_successor(struct rb_tree_node *node);

/**
 * function: search the predecessor of the node
 */
struct rb_tree_node *rb_tree_predecessor(struct rb_tree_node *node);


/**
 * root: I/O, ptr of root the tree
 * z: rb_tree node to be inserted. z should be initialized before calling.
 * cmp: compare function of rb_tree node key
 */
void rb_insert(struct rb_tree_node **root, struct rb_tree_node *z, rb_cmp_func cmp);

/**
 * function: replace u with v, u is picked off the tree
 * root: I/O, ptr of root the tree
 * u: the node to be replaced
 * v: the node to replace u
 */
void rb_transplant(struct rb_tree_node **root, struct rb_tree_node *u, struct rb_tree_node *v);

/**
 * function: delete a node from rb_tree
 * root: I/O, ptr of root of the tree
 * z: the node to be deleted
 */
void rb_delete(struct rb_tree_node **root, struct rb_tree_node *z);


/** 
 * LCS: longgest common subsequence
 */

enum LCS_direct {LCS_MATCH, LCS_UP, LCS_LEFT};

typedef struct
{
    unsigned int **c;   // uint[x.length+1][y.length+1]
                        // suffix is length of head-substring of x and y
                        // c[i][j] contains length of LCS of sub-x and sub-y
    char **b;           // char[x.length][y.length]
                        // suffix is suffix of x and y
} LCS_result;

typedef struct
{
    long i, j;
    char w;
} LCS_sub;

/**
 * function: compute the longest-common-subsequence
 * x: x array address
 * y: y array address
 * xlen: length of x
 * ylen: length of y
 */
LCS_result lcs_length(char *x, char *y, long xlen, long ylen);


/**
 * function: get the LCS
 * b: LCS_result.b returned from lcs_length
 * x: x array address
 * i: length of x
 * j: length of y
 * sub: output. LCS_sub array supplied by caller, it's length is i.
 *      When return, it will contain LCS of x and y,
 * return: length of the LCS
 */
long get_lcs(char **b, char *x, long i, long j, LCS_sub *sub);

/**
 * function: free the memory returned by lcs_length()
 */
void free_lcs(LCS_result lcs, long xlen, long ylen);


/***************************************
 B-TREE
****************************************/

#define B_TREE_T    5   // must be >= 2

struct B_Tree_Node
{
    struct B_Tree_Node *parent;
    struct B_Tree_Node *child[B_TREE_T * 2];
    int key[B_TREE_T * 2 - 1];
    int n;      // number of keys
    int leaf;   // if the node is a leaf
};

typedef struct
{
    struct B_Tree_Node *node;
    int idx;    // index of the key in the node
} Node_Key;

typedef enum
{
    B_OK,           // operation ok
    B_WRONG_PARAM,  // wrong parameter
    B_NOT_FOUND     // no such key when delete
} B_Tree_ACT;

/**
 * function: create a B-Tree node, it contains no keys and is initialized as a leaf
 * return: the new created node
 */
struct B_Tree_Node* btree_create();

/**
 * function: destroy a B-Tree and release the space
 * r: root of a B-TREE
 */
void btree_destroy(struct B_Tree_Node *r);

/**
 * function: judge the node fullness
 * x: the node to be judged
 * return: 1 when full, 0 when non-full
 */
int btree_full(struct B_Tree_Node * x);

/**
 * function: search a key in a B-Tree
 * x: root of a sub B-TREE
 * key: the key to search for
 * return: if found, Node_Key containg the node and index of key
 */
Node_Key btree_search(struct B_Tree_Node *x, int key);

/**
 * function: insert a key into a B-Tree
 * x: root of the B-Tree
 * k: the new key to insert
 * return: the new root of the B-Tree
 */
struct B_Tree_Node* btree_insert(struct B_Tree_Node *r, int k);

/**
 * function: delete a key from a B-Tree
 * root: input/output. root of the B-Tree
 * key: the key to be deleted
 * return: B_OK when deleted, B_NOT_FOUND when no such key
 */
B_Tree_ACT btree_delete(struct B_Tree_Node **root, int key);

/**
 * function: print a B-Tree in vertical
 * r: root of the B-Tree
 * ident: indent for each level of node
 */
void b_print_vertical(struct B_Tree_Node *r, int indent);

/**
 * function: print a B-Tree in horizon
 * r: root of the B-Tree
 * ident: indent for each level of node
 */
void b_print_horizon(struct B_Tree_Node *r, int indent);


/***************************************
 Fibonacci Heap 
****************************************/

struct Fibo_Node
{
    struct Fibo_Node *parent, *child;
    struct Fibo_Node *left, *right;
    long degree;    // number of children
    bool mark;      // whether lost any child since self became a child
};

struct Fibo_Heap
{
    struct Fibo_Node *min;  // point to minimum key Fibo_Node root
    long num;   // number of Fibo_Node in the heap
};


struct Fibo_Node* create_fibo_node();

void init_fibo_node(struct Fibo_Node *node);

struct Fibo_Heap* create_fibo_heap();

/**
 * function: compare fibo-node key, supplied by container
 * return -: n1<n2, 0:n1=n2, +:n1>n2
 */
typedef int (*fibo_cmp_func)(struct Fibo_Node *n1, struct Fibo_Node *n2);

/**
 * function: decrease fibo-node key, supplied by container.
 *           the new key must less than old key
 * n: the fibo-node to decrease key
 * key: point to new key
 * return false: new key not less than old key, true: decrease ok
 */
typedef bool (*fibo_decrease_func)(struct Fibo_Node *n, void *key);

/**
 * function: insert a node of outside world into fibo-heap as a root
 * heap: pointer of fibo-heap
 * node: the fibo-node from the outside world
 * cmp: container supplied comparison function
 */
void fibo_heap_insert(struct Fibo_Heap *heap, struct Fibo_Node *node, fibo_cmp_func cmp);

/**
 * function: remove the minimum key node from the fibo-heap
 * h: concerned fibo-heap
 * cmp: container supplied comparison function
 * return: the picked off node
 */
struct Fibo_Node* fibo_heap_extract_min(struct Fibo_Heap *h, fibo_cmp_func cmp);

/**
 * function: decrease a fibo-node key and adjust the fibo-heap
 * h: concerned fibo-heap
 * n: the fibo-node to decrease key
 * key: point to new key
 * dsc: function to decrease key, supplied by container
 * cmp: function to compare key, supplied by container
 */
void fibo_decrease_key(struct Fibo_Heap *h, struct Fibo_Node *n,
                       void *key, fibo_decrease_func dcs, fibo_cmp_func cmp);


/***************************************
 B-PLUS-TREE
****************************************/

#define BPLUS_TREE_T    3   // must be >= 2

typedef struct BPlus_Tree_Node  BP_Tree_Node;

/**
 * for internal node, child[] contain pointers to children.
 * for leaf node, child[0..BPLUS_TREE_T * 2 - 2] contain pointers to data,
 *     child[BPLUS_TREE_T * 2 - 1] contain pointer to sibling leaf node.
 */
struct BPlus_Tree_Node
{
    BP_Tree_Node *parent;
    BP_Tree_Node *child[BPLUS_TREE_T * 2];
    int key[BPLUS_TREE_T * 2 - 1];  // child(i) < key(i) <= child(i+1)
    int n;      // number of keys
    int leaf;   // if the node is a leaf
};

typedef struct
{
    BP_Tree_Node *node;
    int idx;    // index of the key in the node
} BP_Node_Key;

typedef enum
{
    BP_OK,          // operation ok
    BP_OVERRIDE,    // override when key exist already
    BP_SKIP,        // skip when key exist already
    BP_WRONG_PARAM, // invalid parameter
    BP_NOT_FOUND,   // no such key when delete
    BP_DATA_DELETE, // delete data when found
    BP_DATA_RETURN  // return data when found
} BP_Tree_ACT;

/**
 * function: print a B+-Tree in horizon
 * r: root of the B+-Tree
 * ident: indent for each level of node
 */
void bp_print_horizon(BP_Tree_Node *r, int indent);

/**
 * function: print a B+-Tree in vertical.
 * r: root of the B+-Tree
 */
void bp_print_vertical(BP_Tree_Node *r, int indent);

/**
 * function: print B+-Tree leaf linked-list
 * h: leaf linked-list head
 */
void bp_print_link(BP_Tree_Node *h);

/**
 * function: count depth of B+-Tree node
 * x: the node to count it's depth
 * return: depth of the node, root depth is 0
 */
int bptree_depth(BP_Tree_Node *x);

/**
 * function: create a B+-Tree node, it contains no keys and is initialized as a leaf
 * return: the new created node
 */
BP_Tree_Node* bptree_create();

/**
 * function: destroy a B+-Tree and release the space
 * r: root of a B+-TREE
 */
void bptree_destroy(BP_Tree_Node *r);

/**
 * function: judge the node fullness
 * x: the node to be judged
 * return: 1 when full, 0 when non-full
 */
int bptree_full(BP_Tree_Node * x);

/**
 * function: search a key in a B+-Tree
 * x: root of a sub B+-TREE
 * key: the key to search for
 * return: if found, BP_Node_Key containg the node and index of key
 */
BP_Node_Key bptree_search(BP_Tree_Node *x, int key);

/**
 * function: insert a key into a B+-Tree
 * r: input/output parameter, root of the B+-Tree
 * k: the new key to insert
 * v: the new value to insert
 * act: action to take when key already exist: BP_SKIP, BP_OVERRIDE
 * return: BP_OK, BP_SKIP, BP_OVERRIDE, BP_WRONG_PARAM
 */
BP_Tree_ACT bptree_insert(BP_Tree_Node **r, int k, void *v, BP_Tree_ACT act);

/**
 * function: delete a key
 * r: input/output parameter, root of the B+-Tree
 * k: key to delete
 * act: action to take when key is found: BP_DATA_DELETE, BP_DATA_RETURN
 * v: output. accept the data when act is BP_DATA_RETURN
 * return: BP_OK, BP_WRONG_PARAM, BP_NOT_FOUND, BP_DATA_DELETE, BP_DATA_RETURN
 */
BP_Tree_ACT bptree_delete(BP_Tree_Node **r, int k, BP_Tree_ACT act, void **v);


/*****************************************************************
 queue and stack used in Graph BFS,DFS and other algorithms
******************************************************************/

typedef struct Queue_Node QNode;

typedef struct Queue
{
    QNode *head;
    QNode *tail;
} Queue;

typedef enum
{
    Q_OK,           // operation ok
    Q_DELETE_DATA,  // free the data when destroy queue
    Q_INVALID_PARAM,// wrong parameter
    Q_EMPTY, 
    Q_NO_DATA
} Queue_ACT;


/**
 * function: create a FIFO queue
 * return: the new Queue
 */
Queue* create_queue();

/**
 * function: delete a FIFO queue
 * q: the queue to delete
 * act: action to take while deleting
 * return: should always Q_OK;
 */
Queue_ACT delete_queue(Queue *q, Queue_ACT act);

/**
 * function: test if the queue is empty
 * q: the queue to test
 * return: non-zero: empty, zero: empty
 */
int empty_queue(Queue* q);

/**
 * function: push data to tail
 * q: the queue to push into
 * data: the data to enqueue
 * return: Q_OK when ok, others when wrong
 */
Queue_ACT enqueue(Queue* q, void *data);

/**
 * function: pop data from head
 * q: the queue to pop out
 * data: <output> the pointer to save the data
 * return: Q_OK when ok, others when wrong
 */
Queue_ACT dequeue(Queue* q, void **data);

/**
 * function: merge q2 after q1, then q1 and q2 are freed
 * q1: <input> the first queue, no longer valid afterwards
 * q2: <input> the second queue, no longer valid afterwards
 * q: <output> the merged queue
 */
Queue_ACT merge_queue(Queue *q1, Queue *q2, Queue **q);

/**
 * function: judge if the data is in the queue
 * q: the queue
 * data: the data to search
 * equ: equation function
 * return: the data stored in queue if found, NULL if not found
 */
void* queue_element(Queue* q, void *data, equal_func equ);

/**
 * function: enqueue data sorted by compare function
 * q: the queue
 * data: the data
 * cmp: compare function
 * return: Q_OK when ok, others when wrong
 */
Queue_ACT enqueue_sorted(Queue* q, void *data, cmp_func cmp);

/**
 * function: delete a data from queue
 * q: the queue to pop out
 * data: the data to remove
 * equ: equation function
 * return: Q_OK when ok, others when wrong
 */
Queue_ACT detach_queue(Queue* q, void *data, equal_func equ);

/**
 * function: push data into stack
 * q: the queue to push
 * data: the data to push
 * return: Q_OK when ok, others when wrong
 */
Queue_ACT push(Queue* q, void *data);

/**
 * function: pop data from stack
 * q: the queue to pop
 * data: <output> the data to pop
 * return: Q_OK when ok, others when wrong
 */
Queue_ACT pop(Queue* q, void **data);


/***************************************
 Graph
****************************************/

typedef enum
{
    G_DIRECTED,
    G_UNDIRECTED
} Graph_DIR;

typedef struct Vertex_Node Vertex;
typedef struct
{
    Graph_DIR dir;
    int timing; // used for DFS
    Vertex* v;
} Graph;

typedef enum
{
    G_OK,           // operation ok
    G_VERTEX_DUPLICATE, // there are duplicate vertex
    G_INVALID_PARAM,
    G_INVALID_VERTEX,   // no such vertex
    G_INVALID_GRAPH,    // wrong graph
    G_DIRECTED_CYCLE    // cycle in directed graph
} Graph_ACT;

/**
 * function: create a graph
 * vn: vertex name array
 * num: array size
 * dir: direction of the graph
 * g: <output> the new graph
 * return: G_OK when ok, others when wrong
 */
Graph_ACT create_graph(char *vn[], int num, Graph_DIR dir, Graph** g);

/**
 * function: add a edge from <from> to <to>
 * g: the graph to ad edge
 * from: the start vertex when directed
 * to: the end vertex when directed
 * return: G_OK when ok, others when wrong
 */
Graph_ACT add_edge(Graph *g, char *from, char *to);

/**
 * function: delete a graph
 * g: the graph to delete
 * return: G_OK when ok, others when wrong
 */
Graph_ACT delete_graph(Graph* g);

/**
 * function: BFS(broad-first-search)
 * g: the graph to search
 * source: the source vertex
 * return: G_OK when ok, others when wrong
 */
Graph_ACT graph_bfs(Graph *g, char *source);

/**
 * function: print the BFS path
 * g: the graph after BFS done
 * s: the source vertex
 * v: the target vertex
 * return: G_OK when ok, others when wrong
 */
Graph_ACT print_bfs_path(Graph *g, char *s, char *v);

/**
 * function: DFS(deep-first-search) creating a forest
 * g: the graph to search
 * return: G_OK when ok, others when wrong
 */
Graph_ACT graph_dfs(Graph *g);

/**
 * function: print dfs forest
 * g: the graph
 * return: G_OK when ok, others when wrong
 */
Graph_ACT print_dfs_forest(Graph *g);

/**
 * function: compute the strongly-connected-components
 * g: the graph
 * tg: <output> the transpose graph containing SCC
 * return: G_OK when ok, others when wrong
 */
Graph_ACT strongly_conn_components(Graph *g, Graph **tg);

/**
 * prototype of edge wight function
 * u: vertex 1 name
 * v: vertex 2 name
 * return: weight
 */
typedef double (*edge_weight)(char *u, char *v);

/**
 * function: Kruskal algorithm for minimum spanning tree
 * g: the graph
 * w: edge wight function
 * mst: <output> the minimum spanning tree
 * return: G_OK when ok, others when wrong
 */
Graph_ACT mst_kruskal(Graph *g, edge_weight w, Queue** mst);

/**
 * function: print Kruskal minimum spanning tree
 * mst: the MST
 * return: G_OK when ok, others when wrong
 */
Graph_ACT print_kruskal_mst(Queue *mst);

/**
 * function: delete minimum spanning tree
 * mst: the MST
 * return: G_OK when ok, others when wrong
 */
Graph_ACT delete_mst(Queue *mst);

/**
 * function: Prim algorithm for minimum spanning tree
 * g: the graph
 * w: edge wight function
 * r: root of the MST
 * return: G_OK when ok, others when wrong
 */
Graph_ACT mst_prim(Graph *g, edge_weight w, char *r);

/**
 * function: print Prim minimum spanning tree
 * mst: the MST
 * r: root
 * return: G_OK when ok, others when wrong
 */
Graph_ACT print_prim_mst(Graph *mst, char *r);

/**
 * function: Bellman Ford algorithm for the single source shortest path
 *    There may be negative weight edge
 * g: the graph
 * w: edge wight function
 * s: the source vertex
 * return: G_OK when ok, others when wrong
 */
Graph_ACT bellman_ford(Graph *g, edge_weight w, char *s);

/**
 * function: Dijkstra algorithm for the single source shortest path
 *    All edge weight must be non-negative
 * g: the graph
 * w: edge wight function
 * s: the source vertex
 * return: G_OK when ok, others when wrong
 */
Graph_ACT dijkstra(Graph *g, edge_weight w, char *s);

/**
 * function: print single source shortest path
 * g: the graph
 * s: the source vertex
 * return: G_OK when ok, others when wrong
 */
Graph_ACT print_single_source_shortest(Graph *g, char *s);


/***************************************
 Linear-Programming Problem
****************************************/

typedef enum
{
    LG_OK,  // operation ok
    LG_INVALID_PARAM,
    LG_INFEASIBLE,  // linear-programming is infeasible
    LG_UNBOUNDED    // linear-programming is unbounded
} LG_ACT;

#define LG_VN_LENGTH    10

typedef struct
{
    char name[LG_VN_LENGTH];    // variant name
    double value;               // coefficient or value
} LG_Item;

/**
 * function: do linear-programming by simplex
 * M: number of basic variants
 * N: number of non-basic variants
 * A: standard linear-programming constraint matrix[M][N]
 * b: standard linear-programming constraint constant[M]
 * c: target function coefficient[N]
 * x: <output> point to LG_Item[M+N+1]
 */
LG_ACT simplex(int M, int N, double *A[M], double b[M], double c[N], LG_Item *x);


/**************************************************
 Knuth-Morris-Pratt algorithm for string matching
***************************************************/

/**
 * function: Knuth-Morris-Pratt matcher
 * T: the string to match
 * TLEN: length of T
 * P: the pattern to match
 * PLEN: length of P
 * SIZE: character size
 * M: <output> a size_t array to record matching position
 */
void KMP_matcher(void *T, int TLEN, void *P, int PLEN, int SIZE, char *M);

